package com.jiang.专题.动态规划.Q337;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/10 21:17
 */
class Solution {
    public int rob(TreeNode root) {
        int[] dp = dfs(root); // dp[0] 表示偷当前节点的最高金额，dp[1] 表示不偷当前节点的最高金额
        return Math.max(dp[0], dp[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        int[] l = dfs(node.left); // l[0] 表示偷node.left节点最高金额， l[1]表示不偷node.left节点最高金额
        int[] r = dfs(node.right); // r[0] 表示偷node.right节点最高金额， r[1]表示不偷node.right节点最高金额
        // 偷当前节点，那么就不能偷node.left和node.right这两个节点，只能偷临近节点
        int include = node.val + l[1] + r[1];
        // 不偷当前节点，那么就能偷node.left和node.right两个节点，也能偷临近节点
        int exclude = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{include, exclude};
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}